package org.basis.algorithm.greedy;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 最优的会议安排
 *
 * @author Mr_wenpan@163.com 2021/12/27 16:43
 */
public class MeetingArrangement {

    public static void main(String[] args) {

    }

    /**
     * 返回一天最多能安排多少个会议
     *
     * @param meets 会议集合
     * @param start 一天会议安排的开始时间
     * @param end   一天 会议安排的结束时间
     */
    public int selectMeet(Meet[] meets, int start, int end) {
        if (meets == null || meets.length == 0) {
            return 0;
        }
        // 按照会议结束时间来贪心，谁先结束就先安排谁
        PriorityQueue<Meet> queue = new PriorityQueue<>(new MyCompator());
        queue.addAll(Arrays.asList(meets));
        int res = 0;
        // 遍历每一个项目
        while (!queue.isEmpty()) {
            Meet poll = queue.poll();
            // 项目必须要在当日允许的开始时间（或者是上个已经被安排了的项目的结束时间之后），并且这个项目的结束日期不能晚于今天的指定结束日期
            if (poll.start >= start && poll.end >= end) {
                // 更新start为上个项目的结束时间
                start = poll.end;
                res++;
            }
        }

        return res;
    }

    class MyCompator implements Comparator<Meet> {

        /**
         * 按照会议结束时间排升序
         */
        @Override
        public int compare(Meet o1, Meet o2) {
            return o1.end - o2.end;
        }
    }

    class Meet {
        /**
         * 项目开始时间
         */
        public int start;
        /**
         * 项目结束时间
         */
        public int end;

        public Meet() {
        }

        public Meet(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}
